package com.nanbei.btree;

import com.nanbei.tree.BSTNode;

import java.util.Arrays;

/**
 * @ClassDescription: B树节点
 * @JdkVersion: 17
 * @Author: BaoShan.Li
 * @Date: 2024/6/12 22:09
 *
 *
 * 阶（Order）：指所有节点孩子数最大值
 * B树的阶（order）是指一个节点中可以包含的最多子节点数。
 * 如果B树的阶为m，则每个节点最多有m个子节点（因此，每个节点最多有m-1个关键字）。
 *
 * 度（Degree）： 指树中的孩子数
 * B树的度（degree），也称为最小度数（minimum degree），通常用t表示，它是一个节点中必须至少包含的子节点数。
 * 对于一个度为t的B树，每个节点（除了根节点）必须至少有t个子节点，即每个节点至少包含t-1个关键字。
 * 每个节点最多有2t个子节点，即每个节点最多包含2t-1个关键字。
 *
 *
 *
 */
public class BTreeNode {
    // 键
    int[] keys ;

    // 孩子树
    BTreeNode[] children;

    // KEYS中的有效关键字个数；
    int keyNumber;

    // B树的度
    int t;

    // 是否是叶子节点, 默认刚创建的节点为叶子节点；
    boolean leaf = true ;

    public BTreeNode(int t) {
        this.t = t;
        this.children = new BTreeNode[t * 2];
        this.keys = new int[t * 2 - 1];
    }

    public BTreeNode(int[] its) {
        this.keys = its;
    }

    /**
     * B树查找key
     * @param key 要查找的key
     * @return 包含key的节点
     */
    public BTreeNode get(int key){
        int flag = 0;
        while (flag < keyNumber ){
            if (keys[flag] == key){
                return this;
            }
            if (key < keys[flag]){
                break;
            }
            flag++;
        }
        // 如果当前节点为叶子节点 则证明没有找到；
        if (leaf){
            return null;
        }
        // 继续向叶子节点中查找
        return children[flag].get(key);
    }

    // 向keys 指定的索引 index处添加 key
    public void insertKey(int key, int index){
        System.arraycopy(keys,index,keys,index+1,keyNumber -index);
        keys[index] = key;
        keyNumber++;
    }

    // 向 children 指定的索引 index处添加 key
    public void insertChildren(BTreeNode childrenNode, int index){
         System.arraycopy(children,index,children,index+1,keyNumber -index);
        children[index] = childrenNode;
    }

    /**
     * 删除指定下标处的key
     * @param index 下标
     * @return 被删除的key
     */
    int removeKey(int index) {
        int key = keys[index];
        System.arraycopy(keys,index + 1,keys,index,--keyNumber-index);
        return key;
    }

    /**
     * 删除最左侧key
     * @return 被删除的key
     */
    int removeLeftmostKey() {
        return removeKey(0);
    }

    /**
     * 删除最右侧key
     * @return 被删除的key
     */
    int removeRightmostKey() {
        return removeKey(keyNumber-1);
    }

    /**
     * 删除指定下标处的child
     * @param index 下标
     * @return 被删除的children
     */
    BTreeNode removeChild(int index) {
        BTreeNode child = children[index];
        System.arraycopy(children,index+1,children,index,keyNumber -index);
        children[keyNumber] = null;
        return child;
    }

    /**
     * 删除最左侧children
     * @return 被删除的children
     */
    BTreeNode removeLeftmostChild() {
        return removeChild(0);
    }

    /**
     * 删除最右侧children
     * @return 被删除的children
     */
    BTreeNode removeRightmostChild() {
        return removeChild(keyNumber);
    }

    /**
     * 获取指定下标的左兄弟
     *
     * @param index 指定的下标
     * @return 指定下标的左兄弟
     */
    BTreeNode childLeftSibling(int index) {
        return index == 0 ? null : children[index - 1];
    }

    /**
     * 获取指定下标的右兄弟
     *
     * @param index 指定的下标
     * @return 指定下标的左兄弟
     */
    BTreeNode childRightSibling(int index) {
        return index == keyNumber ? null : children[index + 1];
    }

    /**
     * 复制当前节点的所有 key children 到 target 节点
     * @param target target 节点
     */
    void moveToTarget(BTreeNode target) {
        int number = target.keyNumber;
        if (!leaf){
            System.arraycopy(children, 0, target.children, number, keyNumber + 1);
        }

        System.arraycopy(keys, 0, target.keys, number, keyNumber);
        target.keyNumber = number+keyNumber;
    }


    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
    }
}
